数据结构(四) 双向循环链表

又来安利福利了，双向和循环一起了吧，单讲双向没意思，结合在一起就有意思了，看完了第一篇的单链表应该看双向很轻松了。

运行截图

遗憾没有放上查找，请自己加上吧，正序找逆序找都是easy的

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

//双向循环链表  基本操作和单链表差不多，只不过他有自己的回头路了

typedef struct _double_linked_list
{
    int data;//存放数据
     struct _double_linked_list *front;//前指针
     struct _double_linked_list *next;//后指针

}DouLinkedList;

void traversing_postive(DouLinkedList *list)//正序遍历从头到尾
{
   DouLinkedList *p=list->next;
   DouLinkedList *head=list;//起始头位置
   while(p!=head)//循环到头部就停止
   {
        printf("%d  ",p->data);
        p=p->next;
   }
    printf("\n");
}
void traversing_reverse(DouLinkedList *list)
{
        DouLinkedList *p=list->front;
        DouLinkedList *head=list;
        while(p!=head)//循环到头部就停止
        {
             printf("%d  ",p->data);
             p=p->front;
        }
        printf("\n");
}


void create_tail(DouLinkedList *list,const int n)//n还是创建的长度
{
        DouLinkedList *p=list;
        DouLinkedList *head=list;
        p->front=NULL;
        p->next=NULL;

        for(int i=0;i<n;++i)
        {
            DouLinkedList *temp; int data;
            temp=(DouLinkedList*)malloc(sizeof(DouLinkedList));
            printf("请输入第%d个结点的数据\n",i+1);
            scanf("%d",&data);
            temp->data=data;

            head->front=temp;//头的前面指向插入的尾部
            temp->next=head;//尾的下一个指向头部  这样就构成循环链表了
            p->next=temp;
            temp->front=p;
            p=temp;
        }
}


int insert_node(DouLinkedList *list,int pos,int data)
{
        //链表的下标从1开始
        if(pos<1||list==NULL) return -1;//位置小于或者链表是空的 插入失败

        DouLinkedList *head=list;
        DouLinkedList *p=list->next;

        int i=1;//计数i
        while(p!=head)
        {
            if(i==pos) break;//找到前驱点就停止
            ++i;
            p=p->next;
        }
        if(i<pos) return -1;//越界
        DouLinkedList *newNode=(DouLinkedList*)malloc(sizeof(DouLinkedList));
        newNode->data=data;
        newNode->front=p->front;
        p->front->next=newNode;
        newNode->next=p;
        p->front=newNode;

        return 1;
    }

    int delete_node(DouLinkedList *list,int pos)
    {
        if(pos<1||list==NULL) return -1;

        DouLinkedList *p=list->next;
        DouLinkedList *head=list;
        int i=1;
        while(p!=head)
        {
            if(i==pos) break;
            ++i;
            p=p->next;
        }
        if(i<pos) return -1;
        p->front->next=p->next;
        p->next->front=p->front;
        free(p);
        return 1;
}


int main()
{
        DouLinkedList *mylist;
        mylist=(DouLinkedList*)malloc(sizeof(DouLinkedList));//新建一个头节点

        create_tail(mylist,5);
        printf("正序遍历");
        traversing_postive(mylist);
        printf("逆序遍历");
        traversing_reverse(mylist);

        int flag=insert_node(mylist,2,666);//在第二个插入666

        if(flag!=-1) puts("插入成功");
        else puts("插入失败");
        traversing_postive(mylist);

        flag=delete_node(mylist,3);//删除第三个
        if(flag!=-1) puts("删除成功");
        else puts("删除失败");
        traversing_postive(mylist);
        return 0;
}